10062. Сообщите мне частоту!

Найти частоту ASCII кодов символов, которые встречаются в заданном тексте. Текст не содержит символов с первыми 32 и последними 128 ASCII кодами.

Вход. Каждая строка содержит не более 1000 символов и является отдельным тестом.

Выход. Для каждой строки вывести коды символов, в ней встречающихся, вместе с частотой. Символы выводить в возрастающем порядке их частот. Если два символа встречаются одинаковое число раз, то первым следует выводить символ, имеющий больший ASCII код. Между печатью результатов для каждого теста выводить пустую строку.

Пример входа

AAABBC

AAABBCDDE

Пример выхода

67 1
66 2
65 3
 
69 1
67 1
68 2
66 2
65 3

РЕШЕНИЕ

обработка текста, сортировка

Анализ алгоритма

Из условия следует, что входные строки не содержат символов с ASCII кодами от 0 до 31 (первые 32 символа) и с кодами от 128 до 255 (последние 128 символов). Читаем входную строку, вычисляем сколько раз в ней встречается каждая буква. Сортируем ASCII коды символов в соответствии с их частотами и выводим их.

Пример

Рассмотрим первый пример. В строке встречаются три символа: A – 3 раза, B – 2 раза, C – 1 раз. Выводим коды символов их частоты в соответствии с требуемым условием сортировки.

Реализация алгоритма

Частоту встречи символа в тексте и его код объединим в пару pair<int,int>. Эти пары храним в массиве m. Входную строку читаем в массив s. Частоту встречи символа с ASCII кодом i вычисляем в ячейке ascii[i].

vector<pair<int,int> > m;

int ascii[128];

char s[1001];

Функция lt сравнивает две пары (частота встречи символа, код символа). Сначала сравниваются частоты символов. Если они равны, то сортировка производится по убыванию ASCII кодов символов.

int lt(pair<int,int> p1, pair<int,int> p2)

{

if (p1.first < p2.first) return 1;

if ((p1.first == p2.first) && (p1.second > p2.second)) return 1;

return 0;

}

Читаем в цикле входные строки. После вывода результатов для каждого теста (кроме последнего) печатаем пустую строку.

gets(s);

while (1)

{

m.clear();

memset(ascii,0,sizeof(ascii));

Вычисляем частоты символов.

for(i = 0; i < (int)strlen(s); i++) ascii[s[i]]++;

Составляем пары (частота встречи символа, код символа) для всех ASCII кодов от 32 до 127 и сортируем их в соответствии с описанной выше функцией lt.

for(i = 32; i < 128; i++)

if (ascii[i] > 0) m.push_back(make_pair(ascii[i],i));

sort(m.begin(),m.end(),lt);

Выводим ASCII коды символов и их частоты

for(i = 0; i < m.size(); i++)

printf("%d %d\n",m[i].second,m[i].first);

if (!gets(s)) break;

printf("\n");

}